//***********************************************************
//*
//* File:           DumbPlayer.java
//* Author:         Abhinav Kamra
//* Contact:        kamra@cs.columbia.edu
//* Update:         10/03/2004
//*
//* Description:    Dump player for Project 2.  Purely for
//*                 didactic purposes.
//*
//***********************************************************

package paths.g4;

import java.util.*;
import java.io.*;
import java.awt.*;
import java.awt.image.*;
import javax.imageio.*;

import paths.*;
import ui.Util;

public final class G4Player implements IFCPlayer {

    static Random _random;
    static final String _CNAME = "G4 Player";
    static final Color  _CCOLOR = new Color(0.8f, 0.2f, 0.4f);

    Maps _maps;
    ArrayList<City> cities;
    ArrayList<Link> links;

    ArrayList<AllLink> allLinks;

    ArrayList<String> finalCity = new ArrayList<String>() ;
    ArrayList<AllLink> finalLinks = new ArrayList<AllLink>();

    public final class AllLink
    {
    	public String src;
    	public String dest;
    	
        public AllLink( String src, String dest) throws Exception
        {        	
        	this.src = src;
        	this.dest = dest;
        }
        public AllLink( Link link) throws Exception
        {
        	src = link.src;
        	dest = link.dest;
        }
    }
    

    public final class RouteCity
    {
    	ArrayList<String> city;    
    	
    	public RouteCity()
    	{
    		city = new ArrayList<String>() ;  
    	}
    	public RouteCity(RouteCity old)
    	{
//    		city = old.city.clone() ;  

    		city = new ArrayList<String>();
    		for (int i=0; i<old.city.size(); i++){
//      			System.out.println("test1---- "+old.city.size());      		  
    			city.add(old.city.get(i));
//      			System.out.println("test2---- ");      		    		
      		}
    	}
    }
   	ArrayList<RouteCity> routes = new ArrayList<RouteCity>() ;    	
    

    public final class CityState
    {
    	int distance;
    	int flag;   //now we only use 0 2/4 5
    	//0: start, 5: end(which is start); 
    	//1,2:east/west within the edges, langitude larger/smaller ; 
    	//3,4:east/west outside, langitude smaller/larger than start 
    	
    	ArrayList<String> citiesConnect;   
    	public CityState(){
    		distance = 0;
    		flag = 0;
    		citiesConnect = new ArrayList<String>() ;
    	}
    	public CityState( int distance, int flag){
    		this.distance = distance;
    		this.flag = flag;
    		citiesConnect = new ArrayList<String>() ;
    	}
    }

    public final class CityToStart2
    {
    	String city;
    	ArrayList<CityState> cityStates;   
    	
    	public CityToStart2(){
    		city = new String();
    		cityStates = new ArrayList<CityState>() ;
    	}
    	public CityToStart2( String city){
    		this.city = city;
    		cityStates = new ArrayList<CityState>() ;
    	}
    }
    
    ArrayList<CityToStart2> allCities = new ArrayList<CityToStart2>();
//    ArrayList<CityToStart> allCity = new ArrayList<CityToStart>();

    public void getLinks() throws Exception {

    	int type = 0;
    	allLinks = new ArrayList<AllLink>();
    	
	    Iterator<Link> itLink = links.iterator();
	    Iterator<AllLink> itAllLink = allLinks.iterator();

	    while(itLink.hasNext()){
	    	Link l = itLink.next();
	    	
	    	itAllLink = allLinks.iterator();
		    while(itAllLink.hasNext()){
		    	AllLink al = itAllLink.next();
		    	if (al.src== l.src && al.dest==l.dest){
		    		type += 1;
		    	}
		    	else if (al.src== l.dest && al.dest==l.src){
		    		type += 2;
		    	}
		    	if (type == 3)
		    		break;
		    }
		    
		    if(type == 0){  //no link
		    	allLinks.add( new AllLink(l.src, l.dest));
		    	allLinks.add( new AllLink(l.dest, l.src));
		    }
		    //no branches for type== 1 or 2, usually
		    else if(type == 1){  //src to dest
		    	allLinks.add( new AllLink(l.dest, l.src));		    	
		    }
		    else if(type == 2){ //dest to src
		    	allLinks.add( new AllLink(l.src, l.dest));		    	
		    }
		    //if type==3, alreay have this link, do nothing
  	    }

    } //end of getLinks


    int maxX = 1000, maxY = 800;
    public float mapX( float x){
    	return ((x + 10+ 360) * maxX/360 ) % maxX;
    }
    public float mapY( float y){
    	return ((y + 90) * maxY / 180);
    }
    

    
    //    TimeFunction timeFunction;
    public void register(Maps __maps) throws Exception {
	    _maps = __maps;
	    cities = _maps.getCities();
	    links = _maps.getLinks();
	    //timeFunction = _maps.getTimeFunction();
    }

    public Move move() throws Exception {
    	        
    	
	    BufferedImage image;

	    File file = _maps.getBackgroundImage();
	    
	    //to get the background image, do this
	    image = ImageIO.read(file);
	    
	    //get graphics to draw on the image.
	    Graphics2D g = image.createGraphics();

	    int temp = 0;
	if(temp == 1){

		g.setColor(Color.BLUE);
	    Iterator<Link> itLink = links.iterator();
	    //System.out.println("Travel times at midnight:");
	    while(itLink.hasNext()){
	    	Link l = itLink.next();
	    	System.out.println(l.src + " to "+l.dest);
	    	City src = getCityByName(l.src);
	    	City dest = getCityByName(l.dest);
//	    	g.drawLine(src.x, src.y, dest.x, dest.y);
	    	g.drawLine((int)(src.x), (int)(src.y), (int)(dest.x), (int)(dest.y));
	    	
	    }
		
		g.setFont(new Font(g.getFont().getName(), Font.BOLD, 12));
   	    
	    Iterator<City> itCity = cities.iterator();
	    while(itCity.hasNext()){
	    	City city = itCity.next();
	    	System.out.println(city.name);
	    	if(_maps.getStart().equals(city)){
	    		g.setColor(Color.RED);
	    		g.drawString("Start: "+city.name,
	    				((city.x + 10+ 360) * 900/360 ) % 900,
	    				((-city.y + 90) * 400 / 180));		    		
	    	}else{
	    		g.setColor(Color.GREEN);
	    		g.drawString(city.name, ((city.x + 10+ 360) * 900/360 ) % 900,
	    				((-city.y + 90) * 400 / 180));
	    	}
	    }

	}
	else{

		g.setColor(Color.BLUE);
	    Iterator<Link> itLink = links.iterator();
	    //System.out.println("Travel times at midnight:");
	    while(itLink.hasNext()){
	    	Link l = itLink.next();
	    	
//	    	System.out.println(l.src + " to "+l.dest);
	    	City src = getCityByName(l.src);
	    	City dest = getCityByName(l.dest);
//	    	g.drawLine(src.x, src.y, dest.x, dest.y);
	    }
	    //end of link
	    
	    g.setFont(new Font(g.getFont().getName(), Font.BOLD, 18));
		
	    Iterator<City> itCity = cities.iterator();
//	    int index2 = 0;
	    while(itCity.hasNext()){
	    	City city = itCity.next();
	    	
//	    	System.out.println(index2 + " " + city.name);
	//    	index2++;
	    	
	    	
	    	if(_maps.getStart().equals(city)){
	    		g.setColor(Color.RED);
//	    		g.drawString("Start: "+city.name, ((city.x + 10+ 360) * 1000/360 ) % 1000,
	//    				((-city.y + 90) * 800 / 180) - 30);		    		
	    		g.drawString("Start: "+city.name, mapX(city.x),
	    				mapY(-city.y));		    		
	    	}else{
	    		g.setColor(Color.GREEN);
	    		g.drawString(city.name, mapX(city.x),
	    				mapY(-city.y));	
	    	}
	    }  //end of city
	    

	    getLinks();   //get all bi-direction links in "allLinks"
    	System.out.println("Number of cities:" + cities.size());
    	System.out.println("Number of flights:" + allLinks.size());

	    
	    //begin of check distance
	    String startCity = _maps.getStart().name;
	    
	    
	    //tag all the west links with distance
	    allCities = new ArrayList<CityToStart2>();
	    CityToStart2 start2 = new CityToStart2(startCity); //city
	    start2.cityStates.add( new CityState(0, 0 ));  //dist, tag
	    allCities.add(start2);

	    tagDist2(startCity, 0, startCity, 0);
	    //tag to allCities
	    /*
    	System.out.println("2222 - "+allCities.size());
    	for(int i=0; i<allCities.size(); i++)
    	{
        	System.out.println("3333"+ i+ " - "+allCities.get(i).city+" - "
        			+allCities.get(i).cityStates.size());    		
    	}
	    */
	    
	    //find all routes from start to start
	    String startW = new String(startCity);
	    String newCity = new String();
	    
	    Iterator<CityToStart2> itCity3 = allCities.iterator();

	    while(itCity3.hasNext()){
	    	CityToStart2 city2 = itCity3.next();
	    	if (city2.city.equalsIgnoreCase(startW)){

	    		Iterator<CityState> itCS = city2.cityStates.iterator();
			    while(itCS.hasNext()){
			    	CityState cs = itCS.next();
			    	if (cs.distance>2){
			    		RouteCity routeCity = new RouteCity();
//			    		routeCity.city.add(startW);
//			        	System.out.println("4444 ");
			    		getRoutes(startW, cs.distance, routeCity);
	//		        	System.out.println("5555 - "+routes.size());
//			        	System.out.println("5555 - "+cs.distance+" "+routes.size());

			    	}
			    }	
			    break;
	    	} //end of if find the start city
	    }
    	System.out.println("number of routes: "+routes.size());

	    
		//draw the longest route between newCity and the first city
    	City src2 = getCityByName(startCity);
    	City dest2;
    	String src =new String(startCity); 
	    
	    Iterator<RouteCity> itLink2 = routes.iterator();
	    int maxNum = 0;
	    while(itLink2.hasNext()){
	    	RouteCity l = itLink2.next();
	    	if(l.city.size() > maxNum ){
	    		maxNum = l.city.size();
	    	}
	    }
//	    System.out.println("Maximum number of cities:" + maxNum);
    	int indexForShow = 0;
    	
		g.setColor(Color.RED);
	    itLink2 = routes.iterator();
	    //System.out.println("Travel times at midnight:");
	    while(itLink2.hasNext()){
	    	RouteCity l = itLink2.next();

//	    	if(l.city.size()<20) continue;
	    	if(l.city.size()== maxNum)
	    	{
	    		indexForShow ++;
	    	}
	    	
	    	for (int index=0; index<l.city.size(); index++){
	    		
	    		String dest = l.city.get(index);
		    	dest2 = getCityByName(dest);
		    	if(index==0){
		    		src2 = getCityByName(startCity);
		    		src =new String(startCity); 
		    	}
		    	if(l.city.size()== maxNum)
		    	{
		    		if(indexForShow == 1)
//		    			g.drawLine(src2.x, src2.y, dest2.x, dest2.y);
//			    	g.drawLine((int)(src2.x), (int)(src2.y), (int)(dest2.x), (int)(dest2.y));
			    	g.drawLine((int)(mapX(src2.x)), (int)(mapY(src2.y)), 
			    			(int)mapX((dest2.x)), (int)(mapY(dest2.y)));
		    	}

		    	if( !finalCity.contains(dest) ){
		    		finalCity.add(dest);
		    	}
		    	
		    	/*
		    	AllLink newAL = new AllLink(src, dest);
		    	if( ! finalLinks.contains(newAL)){
		    		finalLinks.add(newAL);
		    	}	*/
		    	Iterator<AllLink> itAL = finalLinks.iterator();
		    	int flag = 0;
		    	while(itAL.hasNext()){
		    		AllLink newAL = itAL.next();
		    		if(newAL.dest.equalsIgnoreCase(dest) &&
		    				newAL.src.equalsIgnoreCase(src))
		    		{
		    			flag = 1;
		    		}
/*		    		if(newAL.dest.equalsIgnoreCase(src) && flag == 0 &&
		    				newAL.src.equalsIgnoreCase(dest))
		    		{
		    			System.out.println("---" + src + " to " + dest);
		    		}*/
		    	}
		    	if(flag == 0)
	    			finalLinks.add(new AllLink(src, dest));

		    	src2 = dest2;
	    		src = new String( dest);
	    	}

	    }	//end of while    
	    	
	    System.out.println("finalCity "+ finalCity.size());
	    System.out.println("finalLinks "+ finalLinks.size());
	    
	    
	    //////////////////////////////
	    //finalCity, finalLinks, routes/////
	    //////////////////////////////

	} //end of if/else, meaning nothing
	

	    Move RET = new Move(image, "Dumb WSF Map");
	    return RET;
    }
    
    
    
    public void getRoutes (String city, int dist, RouteCity route)
    {
    	Iterator<CityToStart2> itCities = allCities.iterator();
    	Iterator<CityState> itCS;
    	
    	if (dist == 1) //the last city before the start/end
    	{
    		route.city.add(_maps.getStart().name);
    		routes.add(route);
    		return;
    	}
    	
    	while(itCities.hasNext()){
    		CityToStart2 currentCity = itCities.next();
    		
    		if(currentCity.city.equalsIgnoreCase(city)){
    			
//    	    	System.out.println("1------ " + city+ dist);
        		itCS = currentCity.cityStates.iterator();
            	while(itCS.hasNext()){
            		CityState cs = itCS.next();
            		if(cs.distance == dist){
//                		if(currentCity.city.equalsIgnoreCase(city)){
            			//find the start city
//            	    	System.out.println("2------ "+cs.citiesConnect.size());
            			for(int i=0; i<cs.citiesConnect.size(); i++){
//                			System.out.println("111---- "+route.city.size());
                			RouteCity newRoute = new RouteCity(route);
//                			System.out.println("222---- ");
                			String newCity = cs.citiesConnect.get(i);

//                			System.out.println("3------ "+ i + newCity);              	    		
//                   	    	System.out.println(newRoute.city.size());

                	    	if(newRoute.city.size()==0){
                	    		newRoute.city = new ArrayList<String>();
//                    	    	System.out.println("333------ ");
                	    	}
//                	    	System.out.println("444------ ");
                	    	newRoute.city.add(newCity);    
//                   	    	System.out.println(newRoute.city.size());
                	    	
                			//recursive
                			getRoutes(newCity, dist-1, newRoute);
            			}
            			break;
            			
            		} //end of if
        		}  //end of while
            	
    			break;
    			
    		} //end of if
    	} //end of while
    } //end of function    
    
    
    /**
     * calculate the distance of the city to the start city
     * @param city current city
     * @param tag one tag for the direction now
     * @param startCity the start and end city
     * @param distance the number of cities in this route
     */
    public void tagDist2 (String city, int tag, String startCity, int distance)
    {
    	//calculate the west direction
	    int dist = distance + 1;
	    int newtag = 0;
	    
//    	System.out.println("1111 "+ dist+ " " + city);

    	String newCity = new String();
	    
	    Iterator<AllLink> itCity = allLinks.iterator();
//	    Iterator<CityToStart2> itAllCities = allCities.iterator();
//	    Iterator<CityState> itCityState;
	    
	    while(itCity.hasNext()){
	    	AllLink cityCurrent = itCity.next();
	    	if (cityCurrent.src.equalsIgnoreCase(city)){
	    		
	    		//find the start of this link
	    		newCity = cityCurrent.dest;
	    		//end of all the links
	/*    		
	    		if(newCity.equalsIgnoreCase("Adelaide"))
	    		{
	    	    	System.out.println(city+"----to Adelaide --- ");	    			
	    		}
	    		if(city.equalsIgnoreCase("Adelaide"))
	    		{
	    	    	System.out.println("----Adelaide now to--- "+newCity);	    			
	    		}
	        
	    		if(city.equalsIgnoreCase("Adelaide")&&
	    				newCity.equalsIgnoreCase("Perth"))
	    		{
	    	    	System.out.println("----Adelaide to Perth--- ");	    			
	    		}
	    	*/	
    	    	City src = getCityByName(city);
    	    	City dest = getCityByName(newCity);
    	    	City start = getCityByName(startCity);

	    		//tell the tag of new city, 0 2/4 5
	    		if (tag ==0 || tag == 2){
	    	    	//now we are using west direction
	    			if ( ((src.x > dest.x) && (dest.x<start.x))
	    				||	 ((src.x < dest.x) && (dest.x>start.x)) )
	    			{ //within edge
	    				newtag = 2;  //west
	    			}
	    			else if( newCity.equalsIgnoreCase(startCity)){
	    				//go back to the start
	    				newtag = 5;
	    			}
	    			else{
	    				continue;  //do nothing
	    			}		    			
	    		}
/*	    		if (tag ==0 || tag == 2){
	    	    	//now we are using west direction
	    			if (src.x > dest.x){ //within edge
	    				newtag = 2;  //west
	    			}
	    			else if (src.x < dest.x && dest.x > start.x){ //outside the edge
	    				newtag = 4;  //west
	    			}
	    			else if( newCity.equalsIgnoreCase(startCity)){
	    				//go back to the start
	    				newtag = 5;
	    			}
	    			else{
	    				continue;  //do nothing
	    			}		    			
	    		}
	    		else if(tag ==4){  //already outside edge, only once
	    			if (src.x > dest.x && dest.x > start.x){ //within edge
	    				newtag = 4;  //west
	    			}
	    			else if( newCity.equalsIgnoreCase(startCity)){
	    				//go back to the start
	    				newtag = 5;
	    			}
	    			else{
	    				continue;  //do nothing
	    			}		    			
	    			
	    		}*/
	    		else
	    			continue;
	    		
	    		Iterator<CityToStart2> itAllCities = allCities.iterator();
	    		int index=-1;
	    		int flag = 0;
	    	    while(itAllCities.hasNext()){
	    	    	CityToStart2 city2 = itAllCities.next();
	    	    	index ++;

	    	    	//find the distance link of new city
	    	    	if (city2.city.equalsIgnoreCase(newCity)){	    	    		
	    	    		
	    	    		flag = 1;
	    	    		
    	    			CityToStart2 newStart = allCities.get(index);
    	    			Iterator<CityState> itCityState = newStart.cityStates.iterator();

    	    			//record the distance
    	    			//find this distance
	    	    		int index2 = -1;
	    	    		int flag2 = 0;
    	    			while(itCityState.hasNext()){
    	    				index2 ++;
    	    				CityState cs = itCityState.next();
    	    				if (cs.distance == dist){
    	    					//find the same distance
    	    					//add new city
    	    					flag2 = 1;
    	    					CityState newCS = newStart.cityStates.get(index2);
//    	    					newCS.distance = dist; // the same
//    	    					newCS.flag = newtag; // the same
    	    					newCS.citiesConnect.add(city);
    	    					
    	    					//if have this distance, no need to continue
    	    					//because the following is the same
    	    	    			//recurrsive
//    	    					if (newtag != 5 )
//    	    						tagDist2(newCity, newtag, startCity, dist);
    	    					break;
    	    				}
    	    			}
    	    			if (flag2== 0){ //no this distance, add
	    					CityState newCS = new CityState(dist, newtag);
	    					newCS.citiesConnect.add(city);
    						newStart.cityStates.add(newCS);
        	    			//recurrsive
	    					if (newtag != 5 )
	    						tagDist2(newCity, newtag, startCity, dist);
    	    			}
    	    			break;
	    	    	} //end of if (find new city)
	    	    }  //end of while
	    	    
    	    	if(flag == 0){
    	    		//don't have this city, new
	    			CityToStart2 newStart = new CityToStart2(newCity);

	    			CityState newCS = new CityState(dist, newtag);
					newCS.citiesConnect.add(city);
					newStart.cityStates.add(newCS);
	    			allCities.add(newStart);
	    			//recurrsive
					if (newtag != 5 )
						tagDist2(newCity, newtag, startCity, dist);
    	    	}
	    	    
    		} //end of if(source city)
	    	//not source city, go on checking next
	    } //end of while
    	
    } //end of function
    
    
     
    
    
        
    
    
    //    public City getCityByName(String name){
    private City getCityByName(String name){
    	Iterator<City> it = cities.iterator();
    	while(it.hasNext()){
    		City city = it.next();
    		if(name.equalsIgnoreCase(city.name))
    			return city;
    	}
    	return null;
    }
    


    public String name() throws Exception {
        return _CNAME;
    }

    public Color color() throws Exception {
        return _CCOLOR;
    }

    public boolean interactive() throws Exception {
        return false;
    }        

}
